package org.sanguine.study.hometasks.second;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * Graph represents an undirected graph with basic operations for O(1) time complexity.
 * Parallel edges and self-loops are allowed. Class Graph is not thread-safe.
 * 
 * @author Alexey Kuznetsov
 *
 */

public class Graph {
	
	private final int V;
	private int E;
	private Map<Integer, Map<Integer, Integer>> edges; //adjacency matrix for the graph
	
	/*
	 * Create new graph for given number of vertices
	 * @param v - number of vertices (must be greater than zero)
	 * @throws IllegalArgumentException if given number of vertices is not greater than zero
	 */
	
	public Graph(int v) {
		if (v <= 0) throw new IllegalArgumentException("Number of vertices must be greater than zero");
		
		V = v;
		E = 0;
		edges = new HashMap<Integer, Map<Integer, Integer>>();
	}
	
	/**
	 * Add new edge between vertices (undirected).
	 * Count of vertices begins from zero [0, Number Of Vertices - 1] 
	 * @param v - number of first vertex
	 * @param w - number of second vertex
	 * @throws IllegalArgumentException if given number of any vertex is wrong
	 */
	
	public void addEdge(int v, int w) {
		if (v < 0 || v >= V) throw new IllegalArgumentException("Vertex v must be within graph");
		if (w < 0 || w >= V) throw new IllegalArgumentException("Vertex w must be within graph");
		
		Map<Integer, Integer> adj = edges.get(v);
		if (adj != null) {
			Integer numberOfEdgesToW = adj.get(w);
			if (numberOfEdgesToW != null) adj.put(w, numberOfEdgesToW + 1);
			else adj.put(w, 1);
		} else {
			adj = new HashMap<>();
			adj.put(w, 1);
			edges.put(v, adj);
		}

		adj = edges.get(w);
		if (adj != null) {
			Integer numberOfEdgesToV = adj.get(v);
			if (numberOfEdgesToV != null) adj.put(v, numberOfEdgesToV + 1);
			else adj.put(v, 1);
		} else {
			adj = new HashMap<>();
			adj.put(v, 1);
			edges.put(w, adj);
		}
		
		E++;
	}
	
	/**
	 * Remove edge between vertices.
	 * Count of vertices begins from zero [0, Number Of Vertices - 1] 
	 * @param v - number of first vertex
	 * @param w - number of second vertex
	 * @return true if given edge removed, false - otherwise
	 * @throws 	IllegalArgumentException if given number of any vertex is wrong,
	 * 			IllegalStateException if inner dataset is broken.
	 */
	
	public boolean removeEdge(int v, int w) {
		if (v < 0 || v >= V) throw new IllegalArgumentException("Vertex v must be within graph");
		if (w < 0 || w >= V) throw new IllegalArgumentException("Vertex w must be within graph");

		Map<Integer, Integer> adj = edges.get(v);
		if (adj != null) {
			Integer numberOfEdgesToW = adj.get(w);
			if (numberOfEdgesToW != null) 
				if (numberOfEdgesToW == 1) {
					adj.remove(w);
					if (adj.isEmpty()) edges.remove(v);
				}
				else adj.put(w, numberOfEdgesToW - 1);
			else return false;
		} else return false;

		adj = edges.get(w);
		if (adj != null) {
			Integer numberOfEdgesToV = adj.get(v);
			if (numberOfEdgesToV != null) 
				if (numberOfEdgesToV == 1) {
					adj.remove(v);
					if (adj.isEmpty()) edges.remove(w);
				} else adj.put(v, numberOfEdgesToV - 1);
			else throw new IllegalStateException("Inner state of dataset is broken: vertex v is present but w is not.");
		} else throw new IllegalStateException("Inner state of dataset is broken: vertex v is present but w is not.");
		
		E--;
		return true;
	}
	
	/**
	 * Check connectivity between vertices (undirected).
	 * Count of vertices begins from zero [0, Number Of Vertices - 1] 
	 * @param v - number of first vertex
	 * @param w - number of second vertex
	 * @return true if connectivity exists, false - otherwise
	 * @throws IllegalArgumentException if given number of any vertex is wrong
	 */

	public boolean isConnectedVertices(int v, int w) {
		if (v < 0 || v >= V) throw new IllegalArgumentException("Vertex v must be within graph");
		if (w < 0 || w >= V) throw new IllegalArgumentException("Vertex w must be within graph");
		
		Map<Integer, Integer> adj = edges.get(v);
		return (adj != null && adj.get(w) != null);
	}
	
	/**
	 * Get all edges for given vertex
	 * @param v - number of vertex ([0, Number Of Vertices - 1])
	 * @return adjacency vector for given vertex as unmodifiable Map<Integer, Integer>,
	 * where the key is the number of linked vertex and value is the number of edges to linked vertex.
	 * @throws IllegalArgumentException if given number of any vertex is wrong
	 */
	
	public Map<Integer, Integer> getEdgesForVertex(int v) {
		if (v < 0 || v >= V) throw new IllegalArgumentException("Vertex v must be within graph");
		
		Map<Integer, Integer> adj = edges.get(v);
		if (adj == null) {
			Map<Integer, Integer> empty = Collections.emptyMap();
			return empty;
		}
		return Collections.unmodifiableMap(adj); 
	}
	
	/**
	 * Get number of vertices
	 * @return number of vertices
	 */
	
	public int getNumberOfVertices() {
		return V;
	}
	
	/**
	 * Get number of edges in graph
	 * @return number of edges
	 */
	
	public int getNumberOfEdges() {
		return E;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + E;
		result = prime * result + V;
		result = prime * result + ((edges == null) ? 0 : edges.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Graph))
			return false;
		Graph other = (Graph) obj;
		if (E != other.E)
			return false;
		if (V != other.V)
			return false;
		if (edges == null) {
			if (other.edges != null)
				return false;
		} else if (!edges.equals(other.edges))
			return false;
		return true;
	}
}
